Computer data is typically stored as a series of binary `1`s and `0`s defining a word, where each binary word is stored in a memory such as a shift register. Detecting the position of the first (or leading) binary `1` in a binary sequence is often desirable for computer related operations. For instance, it is necessary to detect the position of the leading `1` to perform floating point addition and subtraction, to convert integers to floating point representations, and to normalize a floating point representation to maximize precision.
FIG. 1 shows the IEEE (Institute of Electrical and Electronics Engineers) double precision floating point data format (ANSI/IEEE Std. 754-1985). This format is employed in nearly all floating point microprocessors, including the Intel 8087/287/387 series and the Motorola 68881, and is therefore virtually universal in microcomputers that use these microprocessors including IBM Personal Computers.
The data format shown in FIG. 1 comprises 64 bits, B.sub.0 to B.sub.63. The mantissa or fractional part 10 comprises 52 bits, B.sub.0 to B.sub.51, representing the significant digits of the number to be represented. The exponential part 12 comprises 11 bits, B.sub.52 to B.sub.62, and is a power of 2 multiplier applied to the mantissa 10. The exponent is "biased" by adding 1024, so that the exponent field "01111111111" corresponding to bits B.sub.62 to B.sub.52 respectively, represents a numerical exponent of zero. Thus the decimal equivalent of the binary exponential part 12 may range from -1023 to +1024 indicating that the mantissa 10 may be multiplied by powers of 2 between -1023 and 1024. Additionally a sign bit 14 is included as the most significant bit (MSB) B.sub.63 of the entire 64-bit word and identifies the sign of the mantissa 10.
If M is the value of the mantissa 10 and E is the value of the exponential part 12, then the value of the number represented by the 64-bit word of FIG. 1 is: EQU .+-.M(B.sup.E-1024)
where B is the standard base value. For instance, where each bit is a binary digit, i.e. `1` or `0`, the base B is 2.
To achieve even greater precision, the mantissa 10 is normalized by shifting it left and decrementing the exponent 12 until the MSB of the mantissa 10, B.sub.51, is a `1`. The resulting value gains the precision in bits equivalent to the number of positions shifted. Since the resulting mantissa will always have a MSB B.sub.51 of `1`, it would be redundant to retain it. The mantissa 10 is, therefore, typically shifted one more position to the left to discard the leading `1` and the exponential part 12 is decremented one more time. The resulting number gains one more bit of precision. The range of numbers which can be represented is .+-.(2.sup.1)(2.sup.-1023) to .+-.(2.sup.1024) or .+-.2.2.times.10.sup.-308 to .+-.1.8.times.10.sup.308.
Thus, to maximize the precision of a floating point number, a leading one detector (LOD) may be used to locate the position of the leading `1` in the mantissa 10 and encode its position in a binary word. A resulting encoded word specifies the number of times the mantissa 10 is to be shifted to position the leading `1`, one position beyond the MSB of the mantissa 10 or one position left of bit B.sub.51 so that it can be discarded. Shifters may be used to carry out this operation. The bits which store the mantissa are then shifted according to the value of the encoded word and the bits of the exponential part 12 are correspondingly decremented with the aid of other circuitry.
Another example of the use of a leading one detector is for integer-to-floating point conversions. Consider the example of a double precision integer which contains 64 bits, B.sub.63 -B.sub.0, one of which is a sign bit B.sub.63 and the other 63 bits represent the value of an integer. In order to execute the integer-to-floating point conversion, the 63 bits of the integer are mapped into the 52 bit mantissa 10 of the floating point data format shown in FIG. 1. When the leading `1` is positioned in the most significant 10 bits, B.sub.62 -B.sub.53, of the integer format, then the integer bits must be shifted right until the leading `1` is shifted to bit B.sub.52. The number of shifts required for the integer-to-floating point conversion is provided in Table 1, below.
TABLE 1 ______________________________________ Integer Leading One Bit Right Shift Amount Position (Encoded LOD Value) ______________________________________ B.sub.62 10 B.sub.61 9 B.sub.60 8 B.sub.59 7 B.sub.58 6 B.sub.57 5 B.sub.56 4 B.sub.55 3 B.sub.54 2 B.sub.53 1 B.sub.52 0 ______________________________________
In this example to determine how many shifts must be made, a bias value of 52 is used. Thus the leading `1` position is determined and the bias value is subtracted from the value of that position (e.g., if the leading `1` position is B.sub.57 then 52 is subtracted from 57 to result in 5 shifts to the right). the resulting values shown in column 2 of Table 1 represent the number of positions that must be shifted for the conversion.
Leading one detectors (LOD) are well known. Some LODs are commercially available, such as Texas Instrument's 4-bit or 8-bit priority encoders, e.g., TI-74LS348. LODs for detecting the position of the leading `1` in a 4-bit or 8-bit binary word typically employ 4 or 8 gate arrays, respectively. One gate array has only the first MSB as an input, the next gate array has the first 2 MSBs as inputs, the third has the first 3 MSBs as inputs, and so forth until the final gate has an input for each bit of the binary word. Leading Zero Detectors (LZD) are also well known and can be used to determine the position of the leading `1`. An 8-bit LZD circuit for implementing this logic is shown in FIG. 2. Seven AND gates are required and the AND gates must be capable of accepting up to 8 inputs. The inputs, B.sub.7 -B.sub.0 are operated on by these seven AND gates according to the following logic equations
______________________________________ G.sub.1 = .sup.-- B.sub.7 & B.sub.6 G.sub.2 = .sup.-- B.sub.7 & .sup.-- B.sub.6 & B.sub.5 G.sub.3 = .sup.-- B.sub.7 & .sup.-- B.sub.6 & .sup.-- B.sub.5 & B.sub.4 G.sub.4 = .sup.-- B.sub.7 & .sup.-- B.sub.6 & .sup.-- B.sub.5 & .sup.-- B.sub.4 & B.sub.3 G.sub.5 = .sup.-- B.sub.7 & .sup.-- B.sub.6 & .sup.-- B.sub.5 & .sup.-- B.sub.4 & .sup.-- B.sub.3 & B.sub.2 G.sub.6 = .sup.-- B.sub. 7 & .sup.-- B.sub.6 & .sup.-- B.sub.5 & .sup.-- B.sub.4 & .sup.-- B.sub.3 & .sup.-- B.sub.2 & B.sub.1 G.sub.7 = .sup.-- B.sub.7 & .sup.-- B.sub.6 & .sup.-- B.sub.5 & .sup.-- B.sub.4 & .sup.-- B.sub.3 & .sup.-- B.sub.2 & .sup.-- B.sub.1 & ______________________________________ B.sub.0
where B is the logic complement of the binary value of B, "&" is a symbol representing the AND operation and G.sub.1 to G.sub.7 are the outputs of the respective gates. Thus, when G.sub.1 is low there is one leading zero, and the leading `1` position is B.sub.6, when G.sub.2 is low there are two leading zeros and the leading `1` position is B.sub.5, and so forth.
The 8-bit LZD shown in FIG. 2 implements the above described logic. It is evident from this design that to increase the size of the binary input to the LZD, the AND gates must likewise be capable of accepting more inputs, i.e., a 32-bit LOD will require 31 gates where each gate accepts up to 32 inputs each. Therefore, this design is not feasible for the larger number of inputs required for many computer-related operations, e.g., locating the leading `1` in a 52-bit mantissa. However, since it is often desired to locate the leading `1` in a larger word, leading one detectors having such capability have been designed.
For example, a 32-bit LZD is described in Flynn, I. Computer Arithmetic and Logic Units, Saunders College Publishing, 1982, pages 120-125 (hereinafter "Flynn"). This LZD is shown in FIG. 3 and employs the programmable logic array (PLA) shown in FIG. 3. However, PLAs involve complicated designs and circuitry to implement the logic. Furthermore, PLAs are not easily altered to provide an output with a constant bias value, if bias value control is desired.
It is well known, that two or more such PLAs could be combined to expand the LZD of FIG. 3 to 64 or more bits. Such a combination is disclosed by Flynn and is often referred to as the carry-chain technique. For instance, Flynn describes the 64-bit LZD shown in FIG. 4 which comprises two 32-bit PLA encoders of the FIG. 3 type connected in series. The most significant 32 bits of the 64-bit input are provided to PLA 16 which determines if a leading one is present in these 32 bits. If no leading one is detected in these most significant bits, PLA 16 enables the second PLA 18 to input the remaining 32 bits and determine the position of the leading `1`, if one is present. Since the detection of the leading `1` is performed on each group of bits in series, this technique introduces substantial circuit delay which increases with each PLA added to the chain. Additionally, it would not be possible to provide an output having a constant bias value using any of the known LODs in a "carry-chain" configuration.
Therefore, there is a need to provide a versatile LOD that is capable of operating on up to 64 or more bits with minimal delay, and which is simple, reliable, and easy and inexpensive to implement. The present invention achieves these goals.